#include<bits/stdc++.h>
#include"PriorityQueue.hpp"

int idx;

void inswap(DataBase<int, int> &pa, DataBase<int, int> &son){
    DataBase<int, int> temp = pa;
    pa = son;
    son = temp;
}

int input_min( std::vector<DataBase<int,int> > & input){
    int ans = input[0].data;
    for (int i = 0; i < input.size();i++){
        if(input[i].data<ans)
            ans = input[i].data;
    }
    return ans;
}

void rand_shuffle( std::vector<DataBase<int,int> > & data){
    for (int i = data.size() - 1; i > 0;  i--){
        inswap(data[i], data[rand() % i]);
    }
}



bool isIncreasing(const std::vector<int> & input)
{
    for(int i = 0; i < input .size() - 1; i++)
        if(input[i] > input[i+1]) return false;
    return true;
}

int min(const std::vector<DataBase<int, int> > & input)
{
    if(input.empty())
        return 0x7fffffff;
    int ans = input[0].data;
    for (int i = 0; i < input.size();i++)
        if(input[i].data < ans)
            ans = input[i].data;
    return ans;
}

void test_buildHeap(){
    std::vector<DataBase<int, int> > input;
    cout << "------------------------" << endl;
    cout << "   Test for buildHeap   " << endl;
    cout << "------------------------" << endl;
    cout << "|    n    |  time(ms)  |" << endl;
    for (int n = 10; n<= 1000000; n*=10){
        for (int k = 0; k < n; k++){
            DataBase<int, int> temp = {(int)(++idx) * 114514, rand()};
            input.push_back(temp);
        }
        int start = clock();
        PriorityQueue<int, int> pq;
        pq.buildHeap(input);
        int cost = (double)(clock() - start) / CLOCKS_PER_SEC * 1000;
        printf("|%9d|%12d|\n", n, cost);
        input.clear();
    }
    cout << "------------------------" << endl;
}

void test_HeapSort(){
    std::vector<DataBase<int, int> > input;
    std::vector< int > ans;
    cout << "-------------------------------------" << endl;
    cout << "          Test for HeapSort          " << endl;
    cout << "-------------------------------------" << endl;
    cout << "|    n    |    time(ms)    |   ans  |" << endl;
    for(int  n = 10; n<= 1000000; n*= 10){
        for (int k = 0; k < n; k++){
            DataBase<int, int> temp = {(int)(++idx) * 114514, rand()};
            input.push_back(temp);
        }
        int start = clock();
        PriorityQueue<int, int> pq;
        pq.buildHeap(input);
        while (!pq.empty())
        {
            ans.push_back(pq.top().data);
            pq.deleteMin();
        }
        int cost = (double)(clock() - start) / CLOCKS_PER_SEC * 1000;
        printf("|%9d|%16d|%s|\n", n, cost, isIncreasing(ans)?"   AC   ":"   WA   ");
        input.clear();
        ans.clear();
    }
    cout << "-------------------------------------" << endl;
}

void test_remove(){
    std::vector<DataBase<int, int> > input;
    PriorityQueue<int, int> pq;
    cout << "--------------------------------------" << endl;
    cout << "      Test for Insert and Remove      " << endl;
    cout << "--------------------------------------" << endl;
    cout << "|       Key       |       Data       |" << endl;
    int n = 20;
    for(int k = 0; k < n; k++)
    {
        DataBase<int, int> temp = {(int)k, rand()};
        input.push_back(temp);
        printf("|%17d|%18d|\n", input.back().key, input.back().data);
        pq.insert(input.back());
    }
    rand_shuffle(input);
    cout << "--------------------------------------" << endl;
    for(int k = 0; k < n-1; k++)
    {
        pq.remove(input[k].key);
        printf("Remove Key %2d,  pq.top()=%d\n", input[k].key, pq.top().data);
    }
    cout << "--------------------------------------" << endl;
}

void test_modify(){
    std::vector<DataBase<int, int> > input;
    PriorityQueue<int, int> pq;
    cout << "--------------------------------------" << endl;
    cout << "      Test for Insert and modify      " << endl;
    cout << "--------------------------------------" << endl;
    cout << "|       Key       |       Data       |" << endl;
    int n = 10;
    for(int k = 0; k < n; k++)
    {
        DataBase<int, int> temp = {(int)k, rand()};
        input.push_back(temp);
        printf("|%17d|%18d|\n", input.back().key, input.back().data);
        pq.insert(input.back());
    }
    cout << "--------------------------------------" << endl;
    for(int k = 0; k < 20; k++)
    {
        int tmp = rand();
        int key = rand() % 10;
        pq.modifyData(key, tmp);
        input[key].data += tmp;
        printf("Modify Key %2d Set Data=%11d,  pq.top()=%d, %s\n", key, tmp, pq.top().data, pq.top().data == input_min(input) ? "AC" : "WA");
    }

    cout << "--------------------------------------" << endl;
}

int main(){
    test_buildHeap();
    test_HeapSort();
    test_remove();
    test_modify();
}